【解题报告】BZOJ 1096 [ZJOI 2007] 仓库建设

发表于 更新于

传送门

$\text{Solution}$

我们先考虑最朴素的 DP，令 $f_i$ 表示上一个仓库建设在第 $i$ 个点的最小花费。

我们有

时间复杂度为 $O(n^3)$ 严重超时，考虑用前缀和进行第一步优化：

我们令 $qi=\sum{j=1}^ipj$, $r_i=\sum{j=1}^ix_jp_j$ ，于是有：

这时预处理的复杂度为 $O(n)$, DP 复杂度为 $O(n^2)$ ，仍不能满足要求。

考虑使用斜率优化 DP

我们假设有决策 $j1$, $j2$ 满足 $j1 < j2$ 且 $j1$ 比 $j2$ 优，即

化简，得

因为 $j1 < j2$ ，所以 $q{j1} < q{j2}$ ， 于是有

令 $Y_i = f_i+r_i$, $X_i=q_i$ ,那么

随着 $i$ 增大，$x_i$ 也会增大，也就是说，存在临界点 $K$ ， 满足

若转移到 $j2+1$ 到 $K$ 的状态， $j1$ 更优

若转移到大于 $K$ 的状态， $j2$ 更优

这时我们观察不等式左侧，这其实就是平面上 $(X{j1}, Y{j1})$ 和 $(X{j2}, Y{j2})$ 两点之间的斜率。

在斜率优化中，斜率反映了两个转移来源的关系，将斜率与其他数值比较是判别两个转移决策孰优孰劣的标准。

考虑存在于候选列表的连续三个可选转移来源 $j1$, $j2$, $j3$ .其中 $j1$, $j2$ 对应的斜率为 $k1$ ,$j2$, $j3$ 对应的斜率为 $k2$ .若 $k1 > k2$ ,由于 $j1 < j2 < j3$ ， $x_i$ 递增，所以 $K$ 递减（比较难想）,此时 当 $j2$ 比 $j1$ 优时，$j3$ 已经比 $j2$ 优了，所以 $j2$ 永远不会被用到，可以直接从决策列表中删除。

这下我们可以看出，决策列表相邻两点的斜率是递增的，画个图的话会发现这些点构成了一个下凸壳我们需要用类似于维护凸包的方法维护这个凸壳。每次选取决策时先将队头不符合条件的决策删掉，此时队头的解就是最优转移来源，然后要将当前的点加入队列，加入时先将所有可以被删掉的决策删掉再加入。

由于每个决策仅进队和出队一次，所以 DP 的复杂度是 $O(n)$ 的，满足要求

$\text{Code}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1000005
int x[N], p[N], c[N], Q[N];
long long q[N], r[N], f[N];
inline double slope(int i, int j) {
	return 1.0 * ((f[i] + r[i]) - (f[j] + r[j])) / (q[i] - q[j]);
}
int main() {
	std::ios::sync_with_stdio(false);
	int n;
	std::cin >> n;
	for (int i = 1; i <= n; i++) {
		std::cin >> x[i] >> p[i] >> c[i]; 
		q[i] = q[i - 1] + p[i];
		r[i] = r[i - 1] + x[i] * p[i];
	}
	memset(f, 0x3f3f3f3f, sizeof f); f[0] = 0;
	for (int i = 1, h = 0, t = 0; i <= n; i++) {
		while (h < t && slope(Q[h], Q[h + 1]) < x[i]) h++;
		int j = Q[h];
		f[i] = f[j] + x[i] * (q[i - 1] - q[j]) - (r[i - 1] - r[j]) + c[i];
		while (h < t && slope(Q[t - 1], Q[t]) > slope(Q[t], i)) t--;
		Q[++t] = i;
	}
	std::cout << f[n] << std::endl;
	return 0;
}